index.md (1165B)
1 +++ 2 title = "Insertion sort" 3 template = "page-math.html" 4 +++ 5 6 # Insertion sort 7 8 like sorting a hand of cards 9 sequence is a sorted part followed by an unsorted part 10 11 algorithm: 12 13 - initially: sorted is only 1 element 14 - loop: while non-sorted has elements 15 - insert first element of unsorted part in correct position of sorted part 16 17 pseudocode: 18 19  20 21 analysis: 22 23 | **line** | **description** | **constant** | 24 | --- | --- | --- | 25 | 1 | nothing | | 26 | 2 | n operations | constant1 n | 27 | 3 | n-1 operations | constant2 (n-1) | 28 | 4 | n-1 operations | constant3 (n-1) | 29 | 5 | worst case if A[i] > key always true<br>for fixed j we do the test j times:<br>$\sum_{j=2}^{n}=\frac{n(n+1)}{2}-1$ | $\text{constant}_4(\frac{1}{2}(n(n+1))-1)$ | 30 | 6 | same, j-1 times assignment | $\text{constant}_5(\frac{1}{2}(n-1)n)$ | 31 | 7 | same, j-1 times assignment | $\text{constant}_6(\frac{1}{2}(n-1)n)$ | 32 | 8 | n-1 operations | $\text{constant}_7 (n-1)$ | 33 34 sum all the constants, results in T(n) of form $an^2+bn+c$. 35 36 We have an² ≤ T(n), so T is in ϴ(n²). 37 therefore the algorithm is quadratic time complexity.